package cyclelistii

type ListNode struct{
	Val int
	Next *ListNode
}

func detectCycle(head *ListNode) *ListNode {
	// 快慢指针检测环
	if head == nil {
		return head
	}
	// 快慢指针 一定在环中相遇
	fast,slow := head,head
	for fast!=nil && fast.Next!=nil {
		fast = fast.Next.Next
		slow = slow.Next
		if fast==slow {
			for slow!=head{
				slow = slow.Next
				head = head.Next
			}
			return head
		}
	}
	// 此时相遇
	// 下面寻找环的入口：
	// x: head-入口  y:入口-相遇点 z:相遇点-入口
	// 慢指针路径：x+y   快指针路程：x+y+n*(y+z)
	// 2(x+y) = x+y+n*(y+z) 
	// x+y = n*(y+z)   -> x=n(y+z)-y=(n-1)(y+z)+z
	// n=1 时  x=z  快指针转了一圈遇到慢指针
	// n>1  fast转n圈才遇到  
	// 那么 从head出发，从相遇节点出发，相遇时即为入口
	return nil
}

func detectCycle1(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil {
        slow = slow.Next
        if fast.Next == nil {
            return nil
        }
        fast = fast.Next.Next
        if fast == slow {
            p := head
            for p != slow {
                p = p.Next
                slow = slow.Next
            }
            return p
        }
    }
    return nil
}